COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	doyle[e84,jmc]		Notes on Doyle's "Circumscription and implicit definability"
C00007 ENDMK
C⊗;
doyle[e84,jmc]		Notes on Doyle's "Circumscription and implicit definability"

It doesn't seem to me that implicit definability is ``essentially the same''
as circumscription, because implicit definability doesn't, so far as
I know, involve minimizing anything.

Doyle's considerations on page 2 suggest to me that what we need
are parametrized theories.  Ideally such a theory has a single
model, at least for some part of the language, and the truth of
any sentence expressed in this part of the language and the value
of any term so expressed can directly be read off from the description
of the theory or model.

Examples:
	If we have equations involving a small finite set of objects, the
parametrization is a listing of the equivalence classes.  We can promptly
get the class name from an object, and the class names are lexically
distinct.  We also have a list of the classes.  This would seem to
permit the truth of any formula or the value of a conditional term
to be computed in O(n) time.  Well, perhaps that's an exaggeration.

	A more complex example much used in AI is an inheritance
hierarchy with exceptions.  Suppose we have a small set of classes
with inheritance except when a subclass is marked differently.  We'll
use attributes of subclasses that come from a small set, i.e. not
merely boolean.  How do we represent this hierarchy so that any formulas
can be decided and terms evaluated?

	Perhaps the third possibility is the general small database,
which we want to represent in a compact way but so that all sentences
in a finite language are decidable and terms evaluatable.  Maybe this
isn't quite enough without set theory, e.g. the question "What things
do elephants fear?''

page 5
	Doyle should emphasize that Beth's definability theorem
applies only to first order logic, and circumscription gives at
first a second order formula.

	Doyle appeals (at the bottom of the page) to a very special
case of collapsibility.

page 6
	Doyle asserts that the circumscription is collapsible
if A(P) is monotone in P.  Remember that only P is considered
variable.  block(b1) ∨ block(b2)  seems to provide a counterexample.

It seems that we can generate the circumscription of P inductively
in case we can write A(P) in the form

	∀x.foo(x) ∨ P(t1) ∧ ... ∧ P(tn) ⊃ P(s1) ∨ ... ∨ P(sm)

Here the t's and s's are terms involving x.  We start with the
approximation P(x) = false.  foo then gives us a choice of some
terms for which P must be true.  Choose one, say s↓k↓1.  If choosing it
doesn't force all P(ti) to be true, we have a minimal model, namely
P is true for the s↓k↓1(x) for each x.  If the P(t↓i(x) are all true
for certain x's, we get another choice to make.  Every sequence (possibly
infinite) of choices gives a minimal model.  The useful cases will be
when the process peters out in a finite number of steps or if the
result of the infinite process is characterizable in some convenient
way.  This presumably generalizes some subcase of the generalized
inductions, since they don't allow disjunctions on the right.